package leetcode.剑指offer.again.剑指;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/9/26 3:03 PM
 * @description：
 */
public class 剑指_I_38_字符串的排列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.permutation("aab")));

    }

    class Solution {

        List<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>();

        public String[] permutation(String s) {
            dfs(s.toCharArray(), new StringBuilder(), 0);
            // String[] ans = new String[list.size()];
            String[] ans = list.toArray(new String[]{});
            for (int i = 0; i < list.size(); i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }

        private void dfs(char[] chars, StringBuilder builder, int factor) {
            if (builder.length() == chars.length) {
                if (set.add(builder.toString())) {
                    list.add(builder.toString());
                }
                return;
            }
            for (int i = 0; i < chars.length; i++) {
                if ((factor & 1 << i) == 0) {
                    StringBuilder builder1 = new StringBuilder(builder);
                    builder1.append(chars[i]);
                    dfs(chars, builder1, factor + (1 << i));
                }
            }
        }
    }
}
